package leetcode_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨
 *LongestConsecutiveSequence_128 给定一个数组 找出连续数字的最大连续个数
 *describe:用map记录边界 每次维护边界 边界里就保存了最长距离
 *2018年5月28日 下午2:02:01
 */
public class LongestConsecutiveSequence_128_ {
	
	public static void main(String[] args) {
		LongestConsecutiveSequence_128_ test=new LongestConsecutiveSequence_128_();
		int nums[]=new int[] {100, 4, 200, 1, 3, 2};
		System.out.println(test.longestConsecutive(nums));
	}
	/**
	 *@author 周杨
	 *describe:先将所有元素入set 然后不断取出元素 判断左有没有值 如果有就跳过 因为一定不是最大值了
	 *否则一直往右找 AC 80%
	 *2019年1月12日 下午7:27:01
	 */
	public int longestConsecutive_(int[] nums) {
		Set<Integer> set=new HashSet<Integer>();
		for(int i:nums)
			set.add(i);
		int max=0;
		for(int now:set) {
			if(!set.contains(now-1)) {
				int offset=1;
				while(set.contains(now+offset)) {
					++offset;
				}
				max=Math.max(max, offset);
			}
		}
		return max;
	}
	
	public int longestConsecutive(int[] nums) {
		List<Integer> list=new ArrayList<Integer>();//map只有边缘保存
		Map<Integer,Integer> edge=new HashMap<Integer,Integer>();//维护每次连续边界
        int res=0;
       
        for(int i:nums) {
        	int now=1;
        	if(list.contains(i))
        		continue;
        	list.add(i);
        	int leftEdge=i,rightEdge=i;
        	if(list.contains(i-1)) {
        		Integer left=edge.get(i-1);
        		leftEdge=left;
        		now+=(i-leftEdge);
        	}
        	if(list.contains(i+1)) {
        		Integer right=edge.get(i+1);
        		rightEdge=right;
        		now+=(rightEdge-i);
        	}
        	res=Math.max(res, now);
        	edge.put(leftEdge, rightEdge);
        	edge.put(rightEdge,leftEdge);
        }
        return res;
    }
	
	public void find(int i) {
		
	}
}
